{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。\n",
    "\n",
    "例如:\n",
    "给定二叉树: `[3,9,20,null,null,15,7],`\n",
    "```\n",
    "    3\n",
    "   / \\\n",
    "  9  20\n",
    "    /  \\\n",
    "   15   7\n",
    "```\n",
    "返回其层次遍历结果：\n",
    "```\n",
    "[\n",
    "  [3],\n",
    "  [9,20],\n",
    "  [15,7]\n",
    "]\n",
    "```\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用了今天刚学的迭代，写了一个"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import *\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = [[root.val]]\n",
    "        queue = [root]\n",
    "\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            data = []\n",
    "            for tree in queue:\n",
    "                if tree.left:\n",
    "                    new_queue.append(tree.left)\n",
    "                    data.append(tree.left.val)\n",
    "                if tree.right:\n",
    "                    new_queue.append(tree.right)\n",
    "                    data.append(tree.right.val)\n",
    "            queue = new_queue\n",
    "            if data:\n",
    "                ans.append(data)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在看看题解的递归算法。。。真的很优雅"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        levels = []\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        def helper(node: TreeNode, level: int):\n",
    "            print(level)\n",
    "            if len(levels) == level:\n",
    "                levels.append([])\n",
    "            \n",
    "            levels[level].append(node.val)\n",
    "            if node.left:\n",
    "                helper(node.left, level + 1)\n",
    "            if node.right:\n",
    "                helper(node.right, level + 1)\n",
    "                \n",
    "        helper(root, 0)\n",
    "        return levels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}